package backtrack;
import java.util.*;
public class _04_39_组合总和 {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	
    	backtracking(candidates,target,0);
    	
//    	for (List<Integer> i : result) {
//			for (int j : i) {
//				System.out.print(j + " ");
//			}
//			System.out.println();
//		}
    	
    	return result;
    }
    
    public void backtracking(int[] candidates, int target, int startIndex) {
    	if(sum >= target) {
    		if(sum == target) {
    			result.add(new ArrayList(item));
    		}
    		return;
    	}
    	
    	for(int i = startIndex; i < candidates.length; i++) {
    		sum += candidates[i];
    		item.add(candidates[i]);
    		backtracking(candidates, target, i);
    		sum -= item.get(item.size() - 1);
    		item.remove(item.size() - 1);
    	}
    }
    
    public static void main(String[] args) {
    	int[] candidates = {2};
    	int target = 1;
		new _04_39_组合总和().combinationSum(candidates, target);
	}
}
